package test1;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Leetcode3 {
    //四数之和
}

class Solution3   {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        int n=nums.length;
        List<List<Integer>>ret=new ArrayList<>();

        for(int a=0;a<n;){
            for(int b=a+1;b<n;){
                //三数的target
                int left=b+1;//三数left
                int right=n-1;//三数right
                long xx=(long)target-nums[a]-nums[b];//三数之和
                while(left<right){
                    int sum=nums[left]+nums[right];
                    if(sum>xx){
                        right--;
                    }else if(sum<xx){
                        left++;
                    }
                    else{//匹配成功
                        //装进容器
                        ret.add(Arrays.asList(nums[a], nums[b], nums[left],nums[right]));
                        left++;
                        right--;
                        //去重
                        while(left<right&&nums[left]==nums[left-1])left++;
                        while(left<right&&nums[right]==nums[right+1])right--;
                    }
                }
                b++;
                while(b<n&&nums[b]==nums[b-1])b++;
            }
            a++;
            while(a<n&&nums[a]==nums[a-1])a++;
        }
        return ret;
    }
}